package 动态规划;

public class 斐波那契数 {
    class Solution{
        public int fib1(int n){
            if (n < 2) return n;
            int a = 0;int b = 1;int c = 0;
            for (int i = 1; i < n; i++) {
                c = a+b;
                a = b;
                b = c;
            }
            return n;
        }


    //非压缩版本
        public int fib(int n){
            if (n<=1) return n;
            int[] dp = new int[n+1];
            dp[0] = 0;
            dp[1] = 1;
            for (int index = 2; index <= n; index++) {
               dp[index] = dp[index - 1] + dp[index - 2];

            }
             return dp[n];
        }
    }
}
